/*
 * One example for NOI CSP-J Lesson 8:
 * <https://courses.fmsoft.cn/plzs/noijunior-other-data-structures.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <algorithm>        // std::max()
#include <string>           // std::string
#include <vector>           // std::vector
#include <iostream>

using namespace std;

size_t max_common_substring(const string& s1, const string& s2)
{
    size_t m = s1.length();
    size_t n = s2.length();

    // 使用一个 m * n 的矩阵来存储子串的最长公共后缀。
    vector<vector<size_t>> lcsuf(m + 1, vector<size_t>(n + 1, 0));

    // 从底向上构建 lcsuf 表。
    size_t ans = 0;
    for (size_t i = 1; i <= m; i++) {
        for (size_t j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                lcsuf[i][j] = lcsuf[i - 1][j - 1] + 1;
                ans = max(ans, lcsuf[i][j]);
            }
            else {
                lcsuf[i][j] = 0;
            }
        }
    }

    return ans;
}

int main()
{
    string s1 = "One example";
    string s2 = "Two examples";
    cout << max_common_substring(s1, s2) << endl;
    return 0;
}

